class Solution:
	# @return a list of lists of string
	def __init__(self):
		self.board = []
		self.n = None
		self.ans = 0

	def totalNQueens(self, n):
		self.n = n
		self.board = [None for i in xrange(n)]
		self.dfs(0)
		return self.ans

	def dfs(self, currCol):
		if currCol >= self.n:
			self.ans += 1
			return
		for i in xrange(self.n):
			bad = False
			for j in xrange(currCol):
				if (self.board[j] == i) or (abs(self.board[j]-i) == abs(j-currCol)):
					bad = True
					break
			if not bad:
				self.board[currCol] = i
				self.dfs(currCol+1)


if __name__ == '__main__':
	so = Solution()
	ans = so.totalNQueens(5)
	print ans

